\documentclass[twoside,a4paper]{article}
\usepackage{geometry}
\geometry{margin=1.5cm, vmargin={0pt,1cm}}
\setlength{\topmargin}{-1cm}
\setlength{\paperheight}{29.7cm}
\setlength{\textheight}{25.3cm}


% useful packages.
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{enumerate}
\usepackage{graphicx}
\usepackage{multicol}
\usepackage{fancyhdr}
\usepackage{layout}
\usepackage{ctex}%引入中文包
\usepackage{graphicx}
\usepackage{subfigure}
\usepackage{float}



\usepackage{listings}
\usepackage{xcolor}      %代码着色宏包
\usepackage{CJK}         %显示中文宏包

\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}
\lstset{
 backgroundcolor=\color{lightgray}, 
 basicstyle = \footnotesize,       
 breakatwhitespace = false,        
 breaklines = true,                 
 captionpos = b,                    
 commentstyle = \color{mygreen}\bfseries,
 extendedchars = false,             
 frame =shadowbox, 
 framerule=0.5pt,
 keepspaces=true,
 keywordstyle=\color{blue}\bfseries, % keyword style
 language = C++,                     % the language of code
 otherkeywords={string}, 
 numbers=left, 
 numbersep=5pt,
 numberstyle=\tiny\color{mygray},
 rulecolor=\color{black},         
 showspaces=false,  
 showstringspaces=false, 
 showtabs=false,    
 stepnumber=1,         
 stringstyle=\color{mymauve},        % string literal style
 tabsize=2,          
 title=\lstname                      
}


% some common command
\newcommand{\dif}{\mathrm{d}}
\newcommand{\avg}[1]{\left\langle #1 \right\rangle}
\newcommand{\difFrac}[2]{\frac{\dif #1}{\dif #2}}
\newcommand{\pdfFrac}[2]{\frac{\partial #1}{\partial #2}}
\newcommand{\OFL}{\mathrm{OFL}}
\newcommand{\UFL}{\mathrm{UFL}}
\newcommand{\fl}{\mathrm{fl}}
\newcommand{\op}{\odot}
\newcommand{\Eabs}{E_{\mathrm{abs}}}
\newcommand{\Erel}{E_{\mathrm{rel}}}

\begin{document}

\pagestyle{fancy}
\fancyhead{}
\lhead{方丹吟 3190102758}
\chead{Bellman-Ford算法的实现}
\rhead{2022.10.18}

\begin{center}
    \LARGE\songti\textbf{Bellman-Ford算法的实现} \\%标题
    \large\kaishu\textbf{方丹吟\qquad 3190102758}%一般是我的姓名
\end{center}

\section*{一、主要实现内容}
\begin{itemize}
\item 在上一次图论作业的基础上，实现 Bellman-Ford 算法。
\end{itemize}

\section*{二、设计}
\subsection*{1.算法思路}
以邻接矩阵为例实现Bellman-Ford算法，步骤如下：
\begin{itemize}

\item 初始化：初始化源点到所有点的距离，并保存到dist数组中。将源点对应的值设为0，其它的点对应的值设为无穷大（表示不可达）。
\item 迭代求解：迭代循环v-1次（等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
\item 检验负权回路：再次遍历途中所有的边（edge（u，v）），如果可以继续松弛，表示途中存在从源点可达的权为负的回路。

\end{itemize}

\subsection*{2.函数代码}

\begin{lstlisting}[caption={Bellman-Ford算法}]
template<class DT>
void Print (AMGraph<DT> graph,int dist[], int n)
{
    cout<<"单元最短路径："<<endl;
    for(int i = 0; i < n; ++i)
    {
        if (dist[i] == inf)
        {
            cout<<"与节点"<<graph.vertex[i]<<"距离->无穷大"<<endl;
        }
        else
        {
            cout<<"与节点"<<graph.vertex[i]<<"最短路径长为："<<dist[i]<<endl;
        }
    }
}

int inf = 1000000; //表示无穷大
template<class DT>
bool BellmanFord(AMGraph<DT> graph, DT src)
{
    int v = graph.NumVertex;  //图中的顶点数
    int e = graph.NumEdge;  //图中的边数
    int dist[v];  //存储距离
    //初始化
    for(int i = 0; i < v; i++)
    {
        dist[i] = inf;
    }
    int x = graph.VertexIndex(src);  //获取该节点的下标
    dist[x] = 0;

    //v-1次循环
    for(int i = 1; i < v; i++)
    {
        for(int m =0; m < v; m++)
        {
            for(int n = 0; n < v; n++)  //遍历每一条边
            {
                if (graph.arc[n][m] !=0 & dist[m] > dist[n] + graph.arc[n][m]) //松弛条件
                    dist[m] = dist[n] + graph.arc[n][m];
            }
        }
    }
    //再遍历一次用于检测负权回路
    bool isBack = false;
    for(int m =0; m < v; m++)
    {
        if (isBack == true)
            break;
        for(int n = 0; n < v; n++)  //遍历每一条边
        {
            if (graph.arc[n][m] !=0 & dist[m] > dist[n] + graph.arc[n][m]) //松弛条件
            {
                isBack = true;
                break;
            }    
        }
    }
    Print(graph,dist,v);
    return isBack;


}


\end{lstlisting}


\begin{itemize}
\item main()函数
\end{itemize}
\begin{lstlisting}
int main()
{
    //测试时统一选邻接矩阵
    int n = 6; //the Number of Edge
    int a[n] = {2,4,7,1,5,8}; //the Name of Vertex
    int e = 10; //the Number of Edge

    AMGraph<int> graphmatrix(a,n,e); //生成一个矩阵
    graphmatrix.Show();
    
    bool result = BellmanFord(graphmatrix,2);
    if(result){
        cout<<"图中存在负边权回路"<<endl;
    }//if
    else{
        cout<<"图中不存在负边权回路"<<endl;
    }//else


    
    return 0;
}


\end{lstlisting}






%\subsection*{} 

\section*{三、结果报告}
\subsection*{1.测试过程}
\begin{itemize}
\item 依次输入边(2,4,3),(2,1,5),(2,7,1),(2,5,7),(4,1,1),(1,2,7),(7,8,6),(7,5,3),(5,2,8),(8,4,1)
\item 依次输入边(2,4,3),(2,1,5),(2,7,1),(2,5,7),(4,1,1),(1,2,7),(7,8,-8),(7,5,3),(5,2,8),(8,4,1)，此时含有负边环
\end{itemize}

\subsection*{2.测试结果}

\begin{figure}[H]
     \centering
     \includegraphics{test1}
     \caption{测试1}
\end{figure}

\begin{figure}[H]
     \centering
     \includegraphics{test2}
     \caption{测试2}
\end{figure}




\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
